/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.graph.algo.ksp.srdrPaths;
import combi.graph.Mask;
import combi.graph.PrefixTree;
import combi.graph.PrefixTreeNode;
import combi.sipper.io.IOSimpleGraph;
import combi.wip.graph.algo.ksp.Ksp_Yen;
import combi.wip.graph.algo.utils.OrderedCouple;
import combi.wip.graph.algo.utils.heaps.BinaryHeap;
import combi.wip.graph.algo.utils.heaps.Heap;

import java.io.IOException;
import java.util.*;

import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedMaskSubgraph;


public class Ksp_Yen_SRDR<V,E extends DefaultWeightedEdge> implements Runnable{

	private DirectedGraph<V, E> graph;
	private V src;
	private V dest;
	private int k;
	private Map<V, Set<V>> twins;
	private double limit = Double.POSITIVE_INFINITY;
	private boolean useRank;

	private Map<List<E>, OrderedCouple<Double, Integer>> cheminsEtScore = new HashMap<List<E>, OrderedCouple<Double, Integer>>(); // score des chemins

	private List<List<E>> paths;

	public static OrderedCouple<Double, Integer> max = new OrderedCouple<Double, Integer>(Double.POSITIVE_INFINITY, Integer.MAX_VALUE);
	public static OrderedCouple<Double, Integer> zero = new OrderedCouple<Double, Integer>(0.0, 0);


	public Ksp_Yen_SRDR(DirectedGraph<V, E> graph, V src, V dest, int k,  Map<V, Set<V>> twins)
	{
		this.graph = graph;
		this.src = src;
		this.dest = dest;
		this.k = k;
		this.cheminsEtScore = new HashMap<List<E>, OrderedCouple<Double, Integer>>();
		this.twins = twins;
		this.limit=Double.POSITIVE_INFINITY;
		this.useRank=false;
		//System.err.println(twins);
	}


	public Ksp_Yen_SRDR(DirectedGraph<V, E> graph, V src, V dest, int k,  Map<V, Set<V>> twins, boolean useRank)
	{
		this.graph = graph;
		this.src = src;
		this.dest = dest;
		this.k = k;
		this.cheminsEtScore = new HashMap<List<E>, OrderedCouple<Double, Integer>>();
		this.twins = twins;
		this.limit=Double.POSITIVE_INFINITY;
		this.useRank=useRank;
		//System.err.println(twins);
	}

	public void setRank(boolean useRank)
	{
		this.useRank=useRank;
	}

	public void setLimit(int limit)
	{
		this.limit=limit;
	}

	public void clear()
	{
		cheminsEtScore.clear();
	}

	private Set<V> getTwins(V v)
	{
		return twins.get(v);
	}

	private OrderedCouple<Double, Integer> add(OrderedCouple<Double, Integer> arg0, OrderedCouple<Double, Integer> arg1)
	{
		return new OrderedCouple<Double, Integer>(arg0.getFirst()+ arg1.getFirst(), arg0.getSecond()+ arg1.getSecond());
	}


	//TODO prendre en compte le vecteur de poids et les jumeaux.
	public void run() {
		ShortestSRDRPath<V,E> dijkstra = new ShortestSRDRPath<V,E>(graph, src, dest, max, zero);
		dijkstra.run();
		PrefixTree<E> chemins = new PrefixTree<E>();
		//Map<List<E>, OrderedCouple<Double, Integer>> scoreCandidats = new HashMap<List<E>, OrderedCouple<Double, Integer>>(); // score des chemins (candidats)
		//SortedSet<List<E>> candidats = new TreeSet<List<E>>(new CompareCandidats<List<E>, OrderedCouple<Double, Integer>>(scoreCandidats));

		Heap<List<E>, OrderedCouple<Double,Integer>> candidats = new BinaryHeap<List<E>,OrderedCouple<Double,Integer>>(max);;
		
		List<E> path = dijkstra.getPathEdgeList();
		//		if(path != null)
		//		{
		//			System.err.println("plus court chemin : " + dijkstra.getPathLength() + ":" + convertEdgesPath2NodesPath(dijkstra.getPathEdgeList()));
		//		}	
		//		else
		//		{
		//			System.err.println("no path");
		//		}
		if (path != null && dijkstra.getPathLength().getFirst() > limit)
		{
			//System.err.println("not selected path");
			path = null;
		}

		if (path != null && !path.isEmpty())
		{ 
			//System.err.println("searching for next shortest paths");
			//graphe modifi� pour les besoins de l'algo
			Mask<V,E> maskModdedGraph = new Mask<V,E>();
			DirectedMaskSubgraph<V, E> moddedGraph = new DirectedMaskSubgraph<V, E>(graph, maskModdedGraph);
			int nb = 0; // nombre de solutions explor�es
			int rank = 0;
			//scoreCandidats.put(path, dijkstra.getPathLength());
			candidats.insert(path,  dijkstra.getPathLength());
			//System.err.println("debut");
			List<E> cheminEnCours = candidats.min();
			OrderedCouple<Double, Integer> score_old = dijkstra.getPathLength();
			//System.err.println(candidats);
			while(!candidats.isEmpty() && rank < k)
			{
				nb++;
				score_old = candidats.getKeyMin();//scoreCandidats.get(cheminEnCours);
				cheminsEtScore.put(cheminEnCours,score_old);
				candidats.removeMin(); // retrait de ce chemin des candidats.
				//System.err.println((rank+1) + ": " + (nb) + "-eme plus court chemin : " + score_old + ":" + convertEdgesPath2NodesPath(cheminEnCours));
				PrefixTreeNode<E> devEdge = chemins.addSequence(cheminEnCours); //ajout du chemin et obtention de l'arc � la suite duquel a lieu la d�viation
				//System.err.print("Point de deviation : " + devEdge.getVal() + "\t");


				LinkedList<E> prefixe = new LinkedList<E>();
				OrderedCouple<Double, Integer> scorePrefixe = new OrderedCouple<Double, Integer>(zero);
				ListIterator<E> suffixe;

				//2.2a- preparation de la recherche de plus courts sous chemins.
				V devNode = null; // noeud de deviation sur le chemin en court.
				if(devEdge == null || devEdge.getVal() == null)
				{
					// pas d'arc : point de deviation = src.
					devNode = src;
					//devEdge = chemins.getSon(cheminEnCours.get(0));// deviation a la racine de l'arbre.
					devEdge = chemins.getRoot();
					suffixe = cheminEnCours.listIterator();
				}
				else
				{
					//pt de deviation = destination de l'arc.
					devNode = graph.getEdgeTarget(devEdge.getVal());
					boolean fini = false;
					//?
					suffixe = cheminEnCours.listIterator(); //ici pour ne pas recalculer la position du pt de deviation.
					//on calcule le poids du prefixe (possible de s'en passer plus tard avec asso score � arbre prefixe?)
					while(suffixe.hasNext() && !fini)
					{
						E n = suffixe.next();
						fini = devEdge.getVal() == n;
						if (!fini)
						{
							prefixe.addLast(n);
							scorePrefixe = add(scorePrefixe,new OrderedCouple<Double, Integer>(graph.getEdgeWeight(n), 1));
						}
						for (V v : getTwins(graph.getEdgeSource(n)))//retrait du noeuds et de ses jumeaux...
						{
							maskModdedGraph.addVertex(v); // noeud a retirer
						}
					}
					prefixe.addLast(devEdge.getVal());
					scorePrefixe = add(scorePrefixe,new OrderedCouple<Double, Integer>(graph.getEdgeWeight(devEdge.getVal()),1));
				}
				//System.err.println("prefixe : " + prefixe);
				E tmp = suffixe.next();
				///System.err.println(tmp);
				PrefixTreeNode<E> edgeTemp = devEdge;
				suffixe.previous();
				V srcTemp = devNode;
				LinkedList<E> candidatPotentiel;
				do{
					if (edgeTemp.getVal() == null) // cas racine
					{
						srcTemp = devNode;
					}
					else
					{
						srcTemp = graph.getEdgeTarget(edgeTemp.getVal());
						//scorePrefixe = scorePrefixe + graph.getEdgeWeight(edgeTemp.getVal());
					}
					for (PrefixTreeNode<E> fils : edgeTemp.getChilds())
					{
						maskModdedGraph.addEdge(fils.getVal());
					}
					//System.err.println("Retrait " + srcTemp + "->" + getTwins(srcTemp));
					for (V v : getTwins(srcTemp))
					{
						maskModdedGraph.addVertex(v);
					}
					maskModdedGraph.removeVertex(srcTemp);
					///	System.err.println("*****");
					///System.err.println("etape : " + etape++);
					///System.err.println("arc d'attaque : " + edgeTemp.getVal());
					//System.err.println("sommet source du sous-graphe : " + srcTemp);
					///System.err.println("fils : " + edgeTemp.getChilds());
					//System.err.println(graph);
					//retrait des voisins deja utilises a partir de ce prefixe.
					///System.err.println("Sommets retires : " + removedNodes);
					//recherche du plus court chemin entre srcTemp et dest.
					//System.err.println(moddedGraph.vertexSet());
					//System.err.println("plus court sous-chemin entre " + srcTemp + " et " + dest + " : ");
					dijkstra = new ShortestSRDRPath<V,E>(moddedGraph, srcTemp, dest, max, zero);
					dijkstra.run();
					List<E> subPath = dijkstra.getPathEdgeList();
					OrderedCouple<Double, Integer> scoreSubPath;
					//System.err.println(subPath);
					if(subPath != null && !subPath.isEmpty())
					{
						scoreSubPath = dijkstra.getPathLength();
						candidatPotentiel = new LinkedList<E>(prefixe);
						///System.err.println("delta : " + delta);
						candidatPotentiel.addAll(subPath);
						OrderedCouple<Double, Integer> score = add(scorePrefixe, scoreSubPath);
						if (score.getFirst() <= limit)
						{
							//scoreCandidats.put(candidatPotentiel, score);
							candidats.insert(candidatPotentiel, score);
							//System.err.println("nouveau candidat : " + prefixe + subPath + " = " + convertEdgesPath2NodesPath(candidatPotentiel));
						}
					}


					//preparation etape suivante
					tmp = suffixe.next();
					prefixe.addLast(tmp);
					scorePrefixe = add(scorePrefixe,new OrderedCouple<Double, Integer>(graph.getEdgeWeight(tmp), 1));
					//System.err.println(tmp);
					edgeTemp = edgeTemp.getSon(tmp);
					//System.err.println(srcTemp);
					maskModdedGraph.addVertex(srcTemp);

					//					System.err.println("Retrait " + srcTemp + "->" + getTwins(srcTemp));
					//					for (V v : getTwins(srcTemp))
					//					{
					//						maskModdedGraph.addVertex(v);
					//					}
				}while(!edgeTemp.isLeaf());

				// rajout des elements supprimes
				maskModdedGraph.clear();

				//scoreCandidats.remove(cheminEnCours);
				///System.err.println("candidats : " + candidats);
				///System.err.println("-----------------------");
				if (! candidats.isEmpty())
				{
					cheminEnCours = candidats.min(); // ajout du plus petit chemin candidat a l'ensemble des solutions

					//if (useRank && scoreCandidats.get(cheminEnCours).getFirst() > score_old.getFirst())
					if (useRank && candidats.getKeyMin().getFirst() > score_old.getFirst())
					{
						rank = nb;
					}
					else if(!useRank)
					{
						rank = nb;
					}
				}
			}

			// sorti de la boucle tq
			//if (!candidats.isEmpty())
			//{
			//	chemins.addSequence(candidats.get(0));
			//}
		}
		//System.err.println(chemins.getNumberOfLeafs() + " path(s) found");
		paths = new LinkedList<List<E>>(chemins.toPaths());
		//		if (!candidats.isEmpty())
		//		{
		//			paths.add(candidats.get(0));
		//			cheminsEtScore.put(candidats.get(0), scoreCandidats.get(candidats.get(0)));	
		//		}
		Collections.sort(paths, new CompareCandidats<List<E>, OrderedCouple<Double, Integer>>(cheminsEtScore));
		candidats.clear();
		//scoreCandidats.clear();
	}


	public Collection<List<E>> getPaths()
	{
		return paths;
	}

	public OrderedCouple<Double, Integer> getScoreChemin(List<DefaultWeightedEdge> path)
	{
		return cheminsEtScore.get(path);
	}

	public List<V> convertEdgesPath2NodesPath(List<E> edgesPath)
	{
		List<V> nodesPath = new LinkedList<V>();
		if (! edgesPath.isEmpty())
		{
			nodesPath.add(graph.getEdgeSource(edgesPath.get(0)));
			for (E e : edgesPath)
			{
				nodesPath.add(graph.getEdgeTarget(e));
			}
		}
		return nodesPath;
	}


	public class CompareCandidats<T, S extends Comparable<S>> implements Comparator<T>
	{

		private Map<T, S> scores;

		public CompareCandidats(Map<T, S> scoreCandidats)
		{
			this.scores = scoreCandidats;
		}

		public int compare(T o1, T o2) {
			//System.err.println(scores.get(o1) + ": " +  o1.toString() + "\n" + scores.get(o2) + ": " + o2.toString());
			return scores.get(o1).compareTo(scores.get(o2));
		}
	}

	public static List<DefaultWeightedEdge> cut (List<DefaultWeightedEdge> l)
	{
		l.remove(l.size()-1);
		l.remove(0);
		return l;
	}

	public static void main(String[] argv) throws IOException
	{
		DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> graph = IOSimpleGraph.load(argv[0]);
		//System.out.println(graph);
		long oldtime;
		long newtime;

		int k = Integer.valueOf(argv[3]);

		Map<Integer, Set<Integer>> twins = new HashMap<Integer, Set<Integer>>();
		for (Integer v : graph.vertexSet())
		{
			Set<Integer> set = new HashSet<Integer>();
			set.add(v);
			twins.put(v, set);
		}
		/*-----------------------------*/
		oldtime = System.currentTimeMillis();
		Ksp_Yen_SRDR<Integer,DefaultWeightedEdge> myksp = 
				new Ksp_Yen_SRDR<Integer,DefaultWeightedEdge>(
						graph, 
						Integer.valueOf(argv[1]),
						Integer.valueOf(argv[2]),
						k,
						twins);
		myksp.run();
		Collection<List<DefaultWeightedEdge>> mypath = myksp.getPaths();
		newtime = System.currentTimeMillis();
		System.out.println(mypath);
		System.out.println("in "+ (newtime - oldtime) + "ms");


		/*-----------------------------*/
		oldtime = System.currentTimeMillis();
		Ksp_Yen<Integer,DefaultWeightedEdge> ksp = new Ksp_Yen<Integer,DefaultWeightedEdge>(graph, Integer.valueOf(argv[1]), Integer.valueOf(argv[2]), k);
		ksp.run();
		Collection<List<DefaultWeightedEdge>> path = ksp.getPaths();
		newtime = System.currentTimeMillis();
		System.out.println(path);
		System.out.println("in "+ (newtime - oldtime) + "ms");

	}


	public void setPathLimit(double lengthPathLimit) {
		this.limit = lengthPathLimit;
	}

}
